﻿/*
题目：省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

https://leetcode.cn/problems/number-of-provinces/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<int> parent;

    int findCircleNum(vector<vector<int>>& v) {
        int n = v.size();
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (v[i][j])    unit(i, j);
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (get_parent(i) == i)   res++;
        }

        return res;
    }

    // 路径压缩
    int get_parent(int x) {
        return parent[x] == x ? x : parent[x] = get_parent(parent[x]);
    }

    void unit(int x, int y) {
        if (x == y) return;

        int i = get_parent(x);
        int j = get_parent(y);

        parent[j] = i;
    }
};